import java.util.Arrays;

/**
 * 剑指 Offer 56 - I. 数组中数字出现的次数
 * https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
 */
public class Solutions_Offer_56_I {
    public static void main(String[] args) {
        int[] nums = {4, 1, 4, 6};  // output: {1, 6} or {6, 1}
//        int[] nums = {1, 2, 10, 4, 1, 4, 3, 3};  // output: {2, 10} or {10, 2}

        int[] result = singleNumbers(nums);
        System.out.println(Arrays.toString(result));
    }

    public static int[] singleNumbers(int[] nums) {
        int twoNumXor = 0;
        // 遍历 nums 数组，最终结果即是那两个只出现一次的数值，所异或的结果
        for (int num : nums) {
            twoNumXor ^= num;
        }
        /**
         * 通过计算得到 twoNumXor 二进制上最低位的 1：one
         * 可将 nums 中全部元素分成 2 组，即 (num & one) == 0 的和不等于 0 的
         * 例如 数组中只出现一次的数：10(0b1010) 与 2(0b0010),得到异或结果 8(0b1000)
         *       1010   10                            0001
         *    ^  0010    2                         ^  0110
         *    ---------                           -----------
         *       1000(最低位上的 1 就是 1000)            0111（最低位上的 1 就是 0001）
         */
        int one = twoNumXor & (-twoNumXor);

        // 只出现一次的数
        int res = 0;
        for (int num : nums) {
            if ((num & one) == 0) {
                // 每个元素都与 one 进行按位与，结果为 0 的是一组，结果不为 0 的是一组
                // 最终的 res 一定是两个只出现一次的元素中的某一个，因为其他元素都出现两次
                // 异或自己本身的结果为 0
                res ^= num;
            }
        }
        // 通过 res 计算得到另一个只出现一次的数，返回结果
        return new int[]{res, twoNumXor ^ res};
    }
}
